// https://leetcode.cn/problems/swap-nodes-in-pairs/description/

// 算法思路总结：
// 1. 使用虚拟头节点简化边界处理
// 2. 三指针法进行节点交换：a、b、c
// 3. 每次交换相邻两个节点的连接关系
// 4. 移动指针到下一组待交换节点前驱
// 5. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>

struct ListNode
{
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int val) : val(val), next(nullptr) {}
    ListNode(int val, ListNode* next) : val(val), next(next) {}
};

ListNode* createLinkedList(const vector<int>& nums)
{
    if (nums.empty()) return nullptr;
    
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    
    for (int num : nums)
    {
        cur->next = new ListNode(num);
        cur = cur->next;
    }
    
    ListNode* head = dummy->next;
    delete dummy;
    return head;
}

void printLinkedList(ListNode* head)
{
    if (!head)
    {
        cout << "空链表" << endl;
        return;
    }
    
    ListNode* cur = head;
    while (cur)
    {
        cout << cur->val;
        if (cur->next)
            cout << " -> ";
        else
            cout << " -> nullptr";
        cur = cur->next;
    }
    cout << endl;
}


class Solution 
{
public:
    ListNode* swapPairs(ListNode* head) 
    {
        auto dummy = new ListNode(-1);
        dummy->next = head;

        for (auto p = dummy ; p->next && p->next->next ; )
        {
            auto a = p->next;
            auto b = a->next;
            auto c = b->next;

            b->next = a;
            a->next = c;
            p->next = b;

            p = a;
        }
        return dummy->next;
    }
};

int main()
{
    vector<int> v1 = {1,2,3,4}, v2 = {};
    auto l1 = createLinkedList(v1), l2 = createLinkedList(v2);

    Solution sol;
    printLinkedList(sol.swapPairs(l1));
    printLinkedList(sol.swapPairs(l2));

    return 0;
}